home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C++ / Applications / Nuntius 1.2 / src / Nuntius / UStatDynArray.cp < prev    next >
Encoding:
Text File  |  1994-02-20  |  5.4 KB  |  213 lines  |  [TEXT/MPS ]
  1. // Copyright © 1992 Peter Speck, speck@dat.ruc.dk. All rights reserved.
  2. // UStatDynArray.cp
  3.  
  4. #include "UStatDynArray.h"
  5. #include "StreamTools.h"
  6.  
  7. #pragma segment MyArray
  8.  
  9. #define qDebugStatDyn qDebug & 0
  10.  
  11. const long kCurrentStatDynVersion = 1;
  12. const long kMinStatDynVersion = 1;
  13.  
  14. PStatDynArray::PStatDynArray()
  15.     : PDynDynArray()
  16. {
  17.     fFreeEntriesList = nil;
  18.     fMaxFreeElementDiff = 0;
  19. }
  20.  
  21. void PStatDynArray::IStatDynArray(long allocChunk, long maxFreeElementDiff)
  22. {
  23.     IDynDynArray(allocChunk);
  24.     FailInfo fi;
  25.     if (fi.Try())
  26.     {
  27.         TSortedLongintList *sl = new TSortedLongintList();
  28.         sl->ISortedLongintList();
  29.         fFreeEntriesList = sl;
  30.         fMaxFreeElementDiff = maxFreeElementDiff;
  31.         fi.Success();
  32.     }
  33.     else // fail
  34.     {
  35.         delete this;
  36.         fi.ReSignal();
  37.     }
  38. }
  39.  
  40. PStatDynArray::~PStatDynArray()
  41. {
  42.     FreeIfObject(fFreeEntriesList); fFreeEntriesList = nil;
  43. }
  44.  
  45. void PStatDynArray::DoRead(TStream *aStream)
  46. {
  47.     long version = aStream->ReadLong();
  48.     MyStreamCheckVersion(version, kMinStatDynVersion, kCurrentStatDynVersion, "PStatDynArray");
  49.     PDynDynArray::DoRead(aStream);
  50.     ReadDynamicArray(aStream, fFreeEntriesList);
  51. #if qDebug
  52.     PStatDynArray::SanityCheck();
  53. #endif
  54. }
  55.  
  56. void PStatDynArray::DoWrite(TStream *aStream)
  57. {
  58.     aStream->WriteLong(kCurrentStatDynVersion);
  59.     PDynDynArray::DoWrite(aStream);
  60.     WriteDynamicArray(aStream, fFreeEntriesList);
  61. }
  62.  
  63. long PStatDynArray::NeededDiskSpace()
  64. {
  65.     return    sizeof(long) + // version number
  66.                     PDynDynArray::NeededDiskSpace() +
  67.                     MyStreamSizeOfDynamicArray(fFreeEntriesList);
  68. }
  69.  
  70. void PStatDynArray::DeleteAll()
  71. {
  72.     fFreeEntriesList->DeleteAll();
  73.     PDynDynArray::DeleteAll();
  74. }
  75.  
  76. void PStatDynArray::DeleteElementAt(ArrayIndex index)
  77. {
  78. #if qDebugStatDyn
  79.     fprintf(stderr, "PStatDynArray::DeleteElementAt(), index = %ld, fSize = %ld\n", index, fSize);
  80. #endif
  81. #if qDebug
  82.     if (fFreeEntriesList->GetIdentityItemNo(index) != kEmptyIndex)
  83.     {
  84.         fprintf(stderr, "PStatDynArray::DeleteElementAt, index = %ld, element is already deleted!\n", index);
  85.         ProgramBreak(gEmptyString);
  86.         return;
  87.     }
  88.     if (index <= 0 || index > GetSize())
  89.     {
  90.         fprintf(stderr, "PStatDynArray::DeleteElementAt(), index = %ld: Bad index [1, %ld]\n", index, GetSize());
  91.         ProgramBreak(gEmptyString);
  92.     }
  93. #endif
  94.     if (index != GetSize())
  95.     {
  96.         fFreeEntriesList->Insert(index);
  97.         return;
  98.     }
  99.     PDynDynArray::DeleteElementAt(index);
  100.     while (true)
  101.     {
  102.         index--;
  103.         if (!index)
  104.             break;
  105.         if (fFreeEntriesList->Last() != index)
  106.             break;
  107.         fFreeEntriesList->Delete(index);
  108.         PDynDynArray::DeleteElementAt(index);
  109.     }
  110. }
  111.  
  112. ArrayIndex PStatDynArray::CreateNewElement(ArrayIndex size)
  113. {
  114.     // if no in list of free entries, create a new
  115.     if (fFreeEntriesList->GetSize() == 0)
  116.     {
  117. #if qDebugStatDyn
  118.     fprintf(stderr, "PStatDynArray::CreateNewElement(), size = %ld, creates new element\n", size);
  119. #endif
  120.         return PDynDynArray::CreateNewElement(size);
  121.     }
  122.     // seek for entry with at least same size
  123.     CLongintIterator iter(fFreeEntriesList);
  124.     long index;
  125.     for (index = iter.FirstLong(); iter.More(); index = iter.NextLong())
  126.     {
  127.         long elmSize = GetElementSize(index);
  128.         if (elmSize >= size && size - elmSize <= fMaxFreeElementDiff)
  129.         {
  130.             fFreeEntriesList->Delete(index);
  131. #if qDebugStatDyn
  132.     fprintf(stderr, "PStatDynArray::CreateNewElement(), size = %ld, found one at %ld with size = %ld\n", size, index, GetElementSize(index));
  133. #endif
  134.             return index;
  135.         }
  136.     }
  137.     // we did not find a free entry that meets our specifications, so create a new entry
  138.     return PDynDynArray::CreateNewElement(size);
  139.  
  140.  
  141. /*    // don't make existing entries bigger as the are never downsized
  142.     // make the first entry the right size
  143.     index = fFreeEntriesList->First();
  144. #if qDebugStatDyn
  145.     fprintf(stderr, "PStatDynArray::CreateNewElement(), size = %ld, resized one at %ld with old size = %ld\n", size, index, GetElementSize(index));
  146. #endif
  147.     SetElementSize(index, size);
  148.     return index;
  149. */
  150. }
  151.  
  152. Boolean PStatDynArray::EntryIsFree(ArrayIndex index)
  153. {
  154.     return fFreeEntriesList->GetIdentityItemNo(index) != kEmptyIndex;
  155. }
  156.  
  157. void PStatDynArray::DebugDump(Boolean verbose)
  158. {
  159.     PDynDynArray::DebugDump(verbose && false);
  160. #if qDebug
  161.     
  162.     long noFreeEntries = fFreeEntriesList->GetSize();
  163.     
  164.     if (!noFreeEntries)
  165.     {
  166.         fprintf(stderr, "No free entries in list.\n");
  167.         return;
  168.     }
  169.     fprintf(stderr, "List of free items:\n");
  170.     long freeSpace = 0;
  171.     CLongintIterator iter(fFreeEntriesList);
  172.     long index;
  173.     for (index = iter.FirstLong(); iter.More(); index = iter.NextLong())
  174.     {
  175.         long size = GetElementSize(index);
  176.         fprintf(stderr, "%6ld:%6ld bytes\n", index, size);
  177.         freeSpace += size;
  178.     }
  179.     long dataSize = GetDataAllocSize();
  180.     fprintf(stderr, "Total:%6ld bytes free in%4ld entries\n", freeSpace, noFreeEntries);
  181.     fprintf(stderr, "Total:%6ld bytes used in%4ld entries\n", dataSize - freeSpace, GetSize() - noFreeEntries);
  182.     if (dataSize > 0)
  183.     {
  184.         long perc = long((100.0 * freeSpace) / dataSize);
  185.         fprintf(stderr, "Total:%6ld%% is free space in array\n", perc);
  186.     }
  187. #endif
  188. }
  189.  
  190. Boolean PStatDynArray::SanityCheck()
  191. {
  192.     Boolean isGood = PDynDynArray::SanityCheck();
  193. #if qDebug
  194.     if (fFreeEntriesList->GetSize() > 0)
  195.     {
  196.         long prev = fFreeEntriesList->At(1);
  197.         long maxIndex = fFreeEntriesList->GetSize();
  198.         for (long index = 2; index <= maxIndex; index++)
  199.         {
  200.             long curr = fFreeEntriesList->At(index);
  201.             if (curr <= prev || curr <= 0 || curr > GetSize())
  202.             {
  203.                 fprintf(stderr, "WRONG: PStatDynArray::SanityCheck, deleted element: %ld (prev = %ld, freeList.fSize = %ld)\n", curr, prev, maxIndex);
  204.                 isGood = false;
  205.             }
  206.         }
  207.     }
  208.     if (!isGood)
  209.         DebugDump(true);
  210. #endif
  211.     return isGood;
  212. }
  213.